package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC211 {
    public long startExecuteTime = System.currentTimeMillis();


    class Node {
        public char val;
        public Map<Character, Node> next;
        public boolean isWordEnd = false;

        public Node(char val) {
            this.val = val;
            this.next = new LinkedHashMap<>();
        }
    }


    class WordDictionary {

        public Node root;

        /**
         * Initialize your data structure here.
         */
        public WordDictionary() {
            this.root = new Node(' ');
        }

        /**
         * Adds a word into the data structure.
         */
        public void addWord(String word) {
            Node cur = root;
            for (char c : word.toCharArray()) {
                if (!cur.next.containsKey(c)) {
                    cur.next.put(c, new Node(c));
                }

                cur = cur.next.get(c);
            }

            cur.isWordEnd = true;
        }

        /**
         * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
         */
        public boolean search(String word) {
            return searchRecur(word, 0, root);
        }

        public boolean searchRecur(String word, int wordPos, Node cur) {
            if (wordPos >= word.length()) return cur.isWordEnd;

            for (int i = wordPos; i < word.length(); i++) {
                char c = word.charAt(i);
                if (c == '.') {
                    for (Character key : cur.next.keySet()) {
                        if (searchRecur(word, i + 1, cur.next.get(key))) return true;
                    }
                    return false;
                } else {
                    if (!cur.next.containsKey(c)) return false;
                    cur = cur.next.get(c);
                }
            }

            return cur.isWordEnd;
        }
    }

    /**
     * Your WordDictionary object will be instantiated and called as such:
     * WordDictionary obj = new WordDictionary();
     * obj.addWord(word);
     * boolean param_2 = obj.search(word);
     */

    public void run() {
        WordDictionary solution = new WordDictionary();
        solution.addWord("bad");
        solution.addWord("dad");
        solution.addWord("mad");

        System.out.println(solution.search("pad")); // return False
        System.out.println(solution.search("bad")); // return True
        System.out.println(solution.search(".ad")); // return True
        System.out.println(solution.search("b..")); // return True
    }

    public static void main(String[] args) throws Exception {
        LC211 an = new LC211();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
